package oj;

import java.util.*;

import java.util.HashMap;

//剑指offer 35：复杂链表的复制：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
public class Solution_offer35_1 {
    public Node copyRandomList(Node head) {
        //方法一：重写创建一个链表用来存放新链表
        //需要一种映射关系，用来做从老结点到新结点的映射
        //Node 不需要重写 hashCode() 方法 和 equals() 方法
        //在默认情况下，hashCode() 每个对象返回一个唯一的值; equals() 比较 ==
        //都符合我们当下的场景
        Map<Node,Node> map = new HashMap<>();
        //复制
        Node ans = new Node(-1);
        Node last = ans;
        Node cur = head;
        while(cur != null){
            Node node = new Node(cur.val);
            node.random = cur.random;
            //cur 指向老结点
            //node 指向新结点
            //保存这种映射关系
            map.put(cur,node);
            //同时，将 node 尾插到结果链表中
            last.next = node;
            last = node;
            cur = cur.next;
        }
        //修改新链表中的 random 关系
        Node newCur = ans.next;
        while(newCur != null){
            if(newCur.random != null){
                //newCur.random 指向的老链表的结点
                //通过 map 这个映射关系，找到新链表中的对应jiedian
                Node newRandom = map.get(newCur.random);
                //修改 node 的random 关系到新链表的结点上
                newCur.random = newRandom;
            }
            newCur = newCur.next;
        }
        return ans.next;
    }
}
